| $\tilde{O}(1)$-Depth Parallel Reachability Faster than Transitive ClosureShimon Kogan, Merav Parter (Weizmann) |
| $L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional GridsChris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John's University); Yuval Rabani (The Hebrew University of Jerusalem); Robert Young (New York University) |
| 3SUM Is Really Hard: A Real-to-Integer ReductionNick Fischer (Max Planck Institute for Informatics); Adam Polak, Jonas Schmidt (Bocconi University) |
| A coarse Menger's Theorem for planar graphsVáclav Blažej, Michał Pilipczuk, Evangelos Protopapas (Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland) |
| A computational phase transition for learning-to-sample from Ising modelsAndrej Risteski (Carnegie Mellon University); Thuy-Duong (June) Vuong (UC San Diego) |
| A Constant Approximation for Non-Uniform k-CenterTanmay Inamdar (Indian Institute of Technology Jodhpur); William Lochet (CNRS, LIRMM); Fahad Panolan (School of Computer Science, University of Leeds) |
| A general framework for geometric problems: Low-dimensionality implies a PTASAlon Hovav, Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University) |
| A Lower Bound for Non-Commutative CircuitsRan Raz (Princeton University) |
| A Polynomial Coreset for Furthest Neighbor in Planar MetricsKacper Kluk (University of Warsaw); Hung Le (University of Massachusetts, Amherst, USA); Wojciech Nadara, Marcin Pilipczuk (University of Warsaw); Hector Tierno, Vinayak Vinayak (University of Massachusetts, Amherst) |
| A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed GraphsKuowen Chen (Tsinghua University); Nicole Wein (University of Michigan, Ann Arbor, USA); Yiran Zhang (Tsinghua University) |
| A Polynomial-Time Algorithm for Variational Inequalities under the Minty ConditionIoannis Anagnostides (Carnegie Mellon University); Gabriele Farina (MIT); Tuomas Sandholm (Carnegie Mellon University); Brian Hu Zhang (MIT) |
| A PTAS for Euclidean Capacitated Vehicle RoutingZachary Friggstad (University of Alberta); Fabrizio Grandoni, Ramin Mousavi (IDSIA, USI-SUPSI); Kinter Ren, Mohammad R. Salavatipour (University of Alberta) |
| A quasipolynomial-time classical algorithm for SYK thermal expectationsAlexander Zlokapa (MIT) |
| A Shortest Augmenting Path Algorithm for Linear Matroid ParityKou Hamada, Satoru Iwata (University of Tokyo) |
| A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree PolynomialsMartino Bernasconi (Bocconi Univeristy); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Gabriele Farina (MIT) |
| Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile StreamsElena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&M University) |
| Almost Optimal Multiple Source Shortest Paths and ReachabilityBarna Saha, Yinzhan Xu, Christopher Ye (University of California, San Diego) |
| An $\Omega ( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data StructuresYoung Kun Ko (Pennsylvania State University) |
| An O(log log n)-Approximation Algorithm for Submodular Unsplittable Flow on a PathAlexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich); Ruilong Zhang (City University of Hong Kong (Dongguan)) |
| Approximate polymorphisms of predicatesYuval Filmus, Yaroslav Alekseev (Technion) |
| Approximate Spanning Tree Counting from Uncorrelated Edge SetsYang Liu, Richard Peng, Junzhao Yang (Carnegie Mellon University) |
| Approximately Efficient Multidimensional Bilateral TradeAviad Rubinstein (Stanford University, USA); Xizhi Tan, Zixin Zhou (Stanford University) |
| Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and UniversalityFrederic Koehler, Pui Kuen Leung (University of Chicago) |
| Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis ConjectureStephen Arndt, Benjamin Moseley (Carnegie Mellon University); Kirk Pruhs (University of Pittsburgh); Chaitanya Swamy (University of Waterloo); Michael Zlatin (Pomona College) |
| Bellman-Ford in Almost-Linear Time for Dense GraphsGeorge Li (Carnegie Mellon University); Jason Li (CMU); Junkai Zhang (Tsinghua University) |
| Better Bounds For Graph ReconstructionAntoni Buraczewski, Paweł Gawrychowski (University of Wrocław) |
| Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2Joshua A. Grochow (University of Colorado—Boulder); Gabor Ivanyos (Hungarian Academy of Sciences); Youming Qiao (University of New South Wales); Xiaorui Sun (University of Illinois Chicago) |
| Branch-width of connectivity functions is fixed-parameter tractableTuukka Korhonen (University of Copenhagen); Sang-il Oum (Institute for Basic Science) |
| Breaking the Barrier of 2 for Approximating Weighted Throughput Maximization via the Sherali-Adams HierarchyAlexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich) |
| Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors ModelDani Dorfman, Simon Döring, Martin Herold, Danupon Nanongkai (Max Planck Institute for Informatics, Saarland Informatics Campus); Daniel Neuen (TU Dresden); Joachim Spoerhase (University of Liverpool); Zihang Wu (Max Planck Institute for Informatics, Saarland Informatics Campus) |
| Certified Randomness without Structure Against Shallow-Query AdversariesDakshita Khurana (UIUC and NTT Research); Bhaskar Roberts, Avishay Tal (UC Berkeley) |
| Circuit Diameter of Polyhedra is Strongly PolynomialBento Natura (Columbia University) |
| Classical Adversarial Fault-Tolerance and PCPsAnurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Louis Golowich (UC Berkeley); Quynh T Nguyen (Harvard University); Umesh Vazirani (UC Berkeley) |
| Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHEJames Bartusek (Columbia); Aparna Gupte (MIT CSAIL); Saachi Mutreja (Columbia); Omri Shmueli (NTT Research) |
| Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense GraphsBernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" and ETH Zurich); Yonggang Jiang (MPIINF); Thatchaphol Saranurak (University of Michigan) |
| Composing Low-Space AlgorithmsEdward Pyne (MIT); Roei Tell (University of Toronto) |
| Compressed Inverse Suffix ArraysSharma V. Thankachan (North Carolina State University) |
| Connectivity augmentation is fixed-parameter tractableTuukka Korhonen, Mikkel Thorup (University of Copenhagen) |
| Conservative Maltsev Constraint Satisfaction ProblemsAndrew Moorhead, Manuel Bodirsky (TU Dresden) |
| Constructive counterexamples to the additivity of minimum output Rényi entropy of quantum channels for all p > 1Harm Derksen (Northeastern University); Benjamin Lovitz (Concordia University) |
| Dense Subset Sum in Multi-DimensionLin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang (Zhejiang University) |
| Derandomized Sunflowers and Radical Lower BoundsBruno Cavalar (University of Oxford); Théo Fabris (University of Copenhagen); Partha Mukhopadhyay (Chennai Mathematical Institute); Srikanth Srinivasan, Amir Yehudayoff (University of Copenhagen) |
| Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ NormsIsaac Hair (UCSB, UCLA); Amit Sahai (UCLA) |
| Direct-product testers and PCPs from coset complexesRyan O'Donnell, Noah G. Singer (Carnegie Mellon University) |
| Distances in Planar Graphs are Almost for Free!Shay Mozes, Daniel Prigan (Reichman University, Israel) |
| DNF formulas are efficiently testable with relative errorWilliam Pires (Columbia); Xi Chen, Toniann Pitassi, Rocco A. Servedio (Columbia University) |
| Doubly-Efficient Interactive Arguments for Bounded-Space from One-Way FunctionsGuy Rothblum (Apple) |
| DQC1-completeness of normalized trace estimation for functions of log-local HamiltoniansZhengfeng Ji (Tsinghua University); Tongyang Li (Peking University); Changpeng Shao (Academy of Mathematics and System Sciences, Chinese Academy of Sciences); Xinzhao Wang (Peking University); Yuxin Zhang (Academy of Mathematics and Systems Science, Chinese Academy of Sciences) |
| Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update TimeSimon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh (ETH Zurich) |
| Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal SpaceGuy E. Blelloch (Carnegie Mellon University); Yang Hu (Tsinghua University); William Kuszmaul (Carnegie Mellon University); Tianxiao Li (Independent Researcher); Renfei Zhou (Carnegie Mellon University) |
| Dynamic Time Warping in the Low-Distance RegimeItai Boneh (University of Wrocław); Shay Golan (Ariel University); Tomasz Kociumaka (Max Planck Institute for Informatics) |
| Efficient and Private Property Testing via IndistinguishabilityCynthia Dwork, Pranay Tankala (Harvard University) |
| Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothingPranav Joshi (California Institute of Technology); Daniel McMorrow (National University of Singapore); Yihan Zhang (University of Bristol); Amitalok J. Budkuley (Indian Institute of Technology Kharagpur); Sidharth Jaggi (University of Bristol) |
| Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expandersVishnu Iyer, Siddhartha Jain (UT Austin); Stephen Jordan, Rolando D. Somma (Google) |
| Efficiently Listing Projected Trees, and Equivalence of Listing and EnumerationKarl Bringmann (ETH Zurich); Nick Fischer (Max Planck Institute for Informatics); Yanheng Wang (ETH Zürich) |
| Error-Correction of Matrix Multiplication Algorithms over IntegersShuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Institute of Science Tokyo) |
| Expanders Meet Reed--Muller: Easy Instances of Noisy k-XORJarosław Błasiok, Paul Lou, Alon Rosen (Bocconi University); Madhu Sudan (Harvard University) |
| Explicit Almost-Optimal ε-Balanced Codes via Free Expander WalksJun-Ting Hsieh (Massachusetts Institute of Technology); Sidhanth Mohanty (Northwestern University); Rachel Yun Zhang (MIT) |
| Explicit Constant-Alphabet Subspace Design CodesRohan Goyal (MIT); Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Massachusetts Institute of Technology) |
| Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking SetsZeyu Guo, Roshan Raj (The Ohio State University); Chong Shangguan (Shandong University); Zihan Zhang (The Ohio State University) |
| Explicit Separations for One-Query Unitary SynthesisFangqi Dong, Alex Lombardi (Princeton University); Fermi Ma (New York University) |
| Exponential lower bounds for depth-3 circuits in small characteristicMichael A. Forbes (University of Illinois at Urbana-Champaign) |
| Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead CommunicationGuangxu Yang, Jiapeng Zhang (University of Southern California) |
| Fast Convergene of Gradient Descent on Random $\ell_{p}$-Norm RegressionYang Liu, Richard Peng, Weina Wang, Junzhao Yang (Carnegie Mellon University) |
| Fast Insertion for Bucketized Cuckoo HashingTolson Bell, William Kuszmaul (Carnegie Mellon University) |
| Faster Approximate Fixed Points of $\ell_\infty$-ContractionsAndrei Feodorov, Sebastian Haslebacher (ETH Zurich) |
| Fault-Tolerant Quantum Computation with Adversarial ErrorsNikolas Breuckmann (University of Bristol); Louis Golowich, Umesh Vazirani (UC Berkeley) |
| Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected OrientationsKristóf Bérczi (Eötvös Loránd University); Florian Hörsch (CISPA Helmholtz Center for Information Security); András Imolay (Eötvös Loránd University); Tamás Schwarcz (London School of Economics and Political Science) |
| Flip Distance Between Triangulations of Convex Polygons is NP-CompleteJoseph Dorfer (Graz University of Technology) |
| FPT Approximation Schemes for Min-Sum Radii and Min-Sum DiametersFabrizio Grandoni (IDSIA, USI-SUPSI); Anupam Gupta (New York University, USA); Jatin Yadav (Indian Institute Of Technology, Delhi) |
| Fully Dynamic Euclidean k-MeansSayan Bhattacharya (University of Warwick, UK); Martin Costa, Ermiya Farokhnejad (University of Warwick); Shaofeng Jiang (Peking University); Yaonan Jin (Huawei); Jianing Lou (Peking University) |
| Gap Amplification for Local Hamiltonians with Combinatorial SoundnessMitali Bafna (University of Washington); Quynh T Nguyen (Harvard University); Tina Zhang (MIT) |
| Gap-Majority Lemmas in Communication ComplexityPachara Sawettamalya, Huacheng Yu (Princeton University) |
| Graph k-Coloring in Sublinear Average TimeCassandra Marcussen (Harvard University); Edward Pyne, Ronitt Rubinfeld (MIT); Asaf Shapira, Shlomo Tauber (Tel Aviv University) |
| Hard CNF Instances for Ideal Proof Systems: The ROABP CaseTuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London) |
| Hereditary 2-WQO Graph Classes Have Bounded Clique-WidthJulien Duron, Nikolas Mählmann, Szymon Toruńczyk (University of Warsaw) |
| Hilbert's Nullstellensatz is in the Counting HierarchyRobert Andrews, Abhibhav Garg, Éric Schost (University of Waterloo) |
| Improved space-time tradeoff for TSP via extremal set systemsJustin Dallant, László Kozma (Dresden University of Technology) |
| Improved Space-Time Tradeoffs for Permutation Problems via Extremal CombinatoricsAfrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang (Utrecht University) |
| Improved Upper Bounds for the Directed Flow-Cut GapGreg Bodwin, Luba Samborska (University of Michigan) |
| Instance-Optimality of Bidirectional PageRank EstimationMikkel Thorup (University of Copenhagen); Hanzhi Wang (The University of Melbourne) |
| k-Clustering via Iterative Randomized RoundingJarosław Byrka (University of Wrocław); Yuhao Guo, Yang Hu (Tsinghua University); Shi Li (Nanjing University); Chengzhang Wan (Tsinghua University); Zaixuan Wang (Nanjing University) |
| Learning Confidence Ellipsoids and Applications to Robust Subspace RecoveryChao Gao (University of Chicago); Liren Shan (Toyota Technological Institute at Chicago); Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University) |
| Limit on the computational power of C-random stringsAlexey Milovanov (University of Lisbon) |
| Linear-Time Encodable and Decodable Quantum Error-Correcting CodesAdam Wills (Center for Theoretical Physics --- a Leinweber Institute, Massachusetts Institute of Technology, Cambridge, MA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Ting-Chun Lin (Department of Physics, University of California at San Diego, La Jolla, CA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Rachel Yun Zhang (CSAIL, Massachusetts Institute of Technology, Cambridge, MA); Min-Hsiu Hsieh (Hon Hai (Foxconn) Research Institute, Taipei, Taiwan) |
| Local Node Differential PrivacySofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov (Boston University) |
| Lower Bounds for Learning Hamiltonians from Time EvolutionZiyun Chen, Jerry Li, Joe Slote (University of Washington) |
| Lower Bounds for PIR with Preprocessing from Blackbox CryptographyAlexander Hoover (Stevens Institute of Technology); Giuseppe Persiano (Università di Salerno); Kevin Yeo (Google) |
| Many Proof Complexity Generators Inside One Demi-Bits GeneratorXin Li (Johns Hopkins University); Hanlin Ren (Institute for Advanced Study); Yan Zhong (Johns Hopkins University) |
| Min-Plus Convolution Lower Bounds via a Higher-Order BSG TheoremNick Fischer (Max Planck Institute for Informatics); Ce Jin (UC Berkeley); Yinzhan Xu (University of California, San Diego) |
| Mixed state tomography reduces to pure state tomographyAngelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley) |
| Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur QueriesHanlin Ren (Institute for Advanced Study); Ryan Williams (MIT) |
| Near-Optimal Space Lower Bounds for Streaming CSPsYumou Fei, Dor Minzer, Shuo Wang (MIT) |
| Nearly Time-Optimal Pure State Tomography with Pauli MeasurementsSabee Grewal (UT Austin); Meghal Gupta (UC Berkeley); William He (Carnegie Mellon University); Aniruddha Sen (UT Austin); Mihir Singhal (UC Berkeley) |
| No Constant-Cost Protocol for Point–Line IncidenceMika Göös (EPFL); Nathaniel Harms (UBC); Florian K. Richter, Anastasia Sofronova (EPFL) |
| Non-existence probabilities and lower tails in the critical regime via Belief PropagationMatthew Jenssen (King's College London); Will Perkins (Georgia Institute of Technology); Aditya Potukuchi (Max Planck Institute for Software Systems); Michael Simkin (MIT) |
| NP-Hardness and a PTAS for the Pinwheel ProblemRobert Kleinberg, Ahan Mishra (Cornell University) |
| Obfuscation of Arbitrary Quantum Circuits (via Subspace-Preserving Pseudorandom Unitary)Er-Cheng Tang (University of Washington); Mi-Ying Miryam Huang (University of Southern California) |
| On Sampling Lower Bounds for PolynomialsMohammad Mahdi Khodabandeh, Igor Shinkar (Simon Fraser University) |
| On the Complexity of Learning Nash EquilibriaOliver Biggar (Columbia University); Christos Papadimitriou (Columbia U); Georgios Piliouras (Google DeepMind / SUTD) |
| On the Existence of Fair Allocations for Goods and Chores under Dissimilar PreferencesEgor Gagushin, Marios Mertzanidis (Purdue University); Alexandros Psomas (Purdue University and Google Research) |
| On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy CryptographyDivesh Aggarwal (National University of Singapore); Aayush Jain (CMU); Huijia (Rachel) Lin (University of Washington); Yuetian Wu (Peking University) |
| On the undecidability of quantum channel capacitiesArchishna Bhattacharyya, Arthur Mehta (University of Ottawa); Yuming Zhao (University of Copenhagen) |
| Online Algorithms via Minimax and Posterior MatchingThomas Kesselheim (University of Bonn); Marco Molinaro (Microsoft Research); Kalen Patton, Sahil Singla (Georgia Institute of Technology) |
| Online Graph Balancing and the Power of Two ChoicesNikhil Bansal, Milind Prabhu (University of Michigan); Sahil Singla (Georgia Institute of Technology); Siddharth Meenachi Sundaram (Georgia Tech) |
| Online Submodular Welfare Maximization: Computation is not the BottleneckRajan Udwani (UC Berkeley); David Wajc (Technion) |
| Optimal algorithm for 2-Approximate All Pair Shortest Paths --- almostManoj Gupta, Mrigankashekhar Shandilya (IIT Gandhinagar) |
| Optimal Bounds for the k-Disjoint Paths ProblemMaximilian Gorsky (Institute for Basic Science); Dario Giuliano Cavallaro, Stephan Kreutzer (TU Berlin); Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France); Sebastian Wiederrecht (KAIST) |
| Optimal FPT-Approximability for Modular Linear EquationsKonrad K. Dabrowski (Newcastle University); Peter Jonsson (Linköping University); Sebastian Ordyniak (University of Leeds, UK); George Osipov (University of Oxford); Magnus Wahlstrom (Royal Holloway, University of London, UK) |
| Optimal Lower Bounds for Online MulticalibrationNatalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth (University of Pennsylvania) |
| Optimal Online Bin Packing under Prophet, Random-Order, and Learning-from-Samples ModelsKailash Gopal Darmasubramanian (Indian Institute of Technology, Madras); Samyak Jha, Arindam Khan, K. V. N. Sreenivas (Indian Institute of Science, Bengaluru) |
| Optimal PSPACE-hardness of Approximating $q$-CSP ReconfigurationShuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.) |
| Optimal Single-Pass Streaming Lower Bounds for Approximating CSPsNoah G. Singer (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Santhoshini Velusamy (University of Waterloo) |
| Overcoming Padding in Cryptography via the Hardness of Certifying Random StringsYao-Ching Hsieh (University of Washington); Abhishek Jain (NTT Research and Johns Hopkins); Jiatu Li (Massachusetts Institute of Technology); Surya Mathialagan (NTT Research) |
| Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic DepthYonggang Jiang (MPIINF); Changki Yun (Seoul National University) |
| Parity ∉ QAC⁰ ⇔ QAC⁰ is Fourier-ConcentratedLucas Gretta, Meghal Gupta, Malvika Raj Joshi (UC Berkeley) |
| Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case AnalysisDeepak Bhati (CISPA Helmholtz Center for Information Security); Pranjal Dutta (Nanyang Technological University, Singapore); Antoine Joux, Mahesh Sreekumar Rajasree (CISPA Helmholtz Center for Information Security); Karol Węgrzycki (Max Planck Institute for Informatics) |
| Polynomial $\chi$-boundedness for excluding $P_5$Tung Nguyen (University of Oxford) |
| PTF Lower Bounds from Low-Degree Testing Lower Bounds in Additive Noise ModelsIlias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Trung Tran (University of California, San Diego) |
| QAC^0 contains TC^0 (with many copies of the input)Daniel Grier, Jackson Morris (University of California, San Diego); Kewen Wu (Institute for Advanced Study) |
| Quality control in sublinear time: a case study via random graphsCassandra Marcussen (Harvard University); Ronitt Rubinfeld (MIT); Madhu Sudan (Harvard University) |
| Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transitionKean Chen (University of Pennsylvania); Filippo Girardi (Scuola Normale Superiore); Aadil Oufkir (University Mohammed VI Polytechnic); Nengkun Yu (Stony Brook University); Zhicheng Zhang (Griffith University) |
| Quantum oracles, weak and strongJohn Wright (The University of California, Berkeley); Ewin Tang (UC Berkeley); Mark Zhandry (Stanford) |
| Quantum Speedups Require Structure or DepthGuy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan (Stanford University) |
| Rapid mixing in positively weighted restricted Boltzmann machinesWeiming Feng (The University of Hong Kong); Heng Guo (University of Edinburgh); Minji Yang (The University of Hong Kong) |
| Rational degree is polynomially related to degreeRobin Kothari (Google); Matt Kovacs-Deak (University of Maryland); Daochen Wang, Rain Zimin Yang (University of British Columbia) |
| Recovering Polynomials over Finite Fields from Noisy Character ValuesSwastik Kopparty (University of Toronto) |
| Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial LearnersIlias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Mingchen Ma (UW-Madison) |
| Robust Learning with Optimal ErrorGuy Blanc (Stanford University) |
| Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-EndSteve Hanneke (Purdue University); Idan Mehalel (The Hebrew University); Shay Moran (Technion and Google Research) |
| Sample-efficient black-box reductions in Bayesian mechanism design with independent itemsArya Maheshwari (Carnegie Mellon University); S. Matthew Weinberg, Eric Xue (Princeton University) |
| Schur complements for tensors and multilinear commutative rankGuy Moshkovitz (City University of New York); Daniel G. Zhu (Princeton University) |
| Separating Quantum and Classical Advice with Good CodesAndrew Huang (MIT); John Bostanci (Columbia University); Vinod Vaikuntanathan (MIT) |
| Separating RAM and Multitape Turing Machines with Short Random OraclesLijie Chen, Yichuan Wang (UC Berkeley) |
| Sharp Lovasz-Theta Bounds on Random GraphsAaron Potechin (University of Chicago); Jeff Xu (TTIC) |
| Short and Sweet: Computationally Efficient Collaborative Communication Through Indistinguishability and CoarseningMark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell (UC Berkeley) |
| Shortest Paths with Linear Edge WeightsSuryajith Chillara, Kshitij Gajjar (International Institute of Information Technology, Hyderabad); Nithish Raja (Eindhoven University of Technology) |
| Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk GraphsMark de Berg (TU Eindhoven); Bart Jansen (TU Eindhoven, the Netherlands); Jeroen S.K. Lamme (TU Eindhoven) |
| Singleton algorithms for the Constraint Satisfaction ProblemDmitriy Zhuk (Charles University, Prague) |
| Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound HeapsDaniel Rutschmann (Institute of Science and Technology Austria (ISTA)) |
| Space-Efficient Simulations Beyond Multitape Turing MachinesDanil Sibgatullin, Ryan Williams (MIT) |
| Stable algorithms cannot reliably find isolated perceptron solutionsShuyang Gong (Peking University); Brice Huang (Stanford University); Shuangping Li (Yale University); Mark Sellke (Harvard University) |
| Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner ProblemsJoseph Koutsoutis, Jesse Lerner, Roie Levin, Jiawei Yu (Rutgers University) |
| Strassen's support functionals coincide with the quantum functionals: a general classical-quantum correspondence for optimization on entanglement polytopes and beyondKeiya Sakabe, Mahmut Levent Doğan, Michael Walter (LMU Munich) |
| Strong Low Degree Hardness for Stable Local Optima in Spin GlassesBrice Huang (Stanford); Mark Sellke (Harvard) |
| Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic MemoryMichael Menart (University of Toronto, Vector Institute); Sasho Nikolov (University of Toronto); Ohad Shamir (Weizmann Institute and University of Toronto) |
| Strongly Refuting Random CSP without LiteralsSiu On Chan (Unaffiliated); Tommaso D'Orsi (Bocconi University); Jeff Xu (TTIC) |
| Subquadratic Counting via Perfect Marginal SamplingXiaoyu Chen (MIT); Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (MIT); Xinyuan Zhang (Nanjing University) |
| Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line SizeSusanna F. de Rezende, David Engström (Lund University); Yassine Ghannane (University of Copenhagen); Kilian Risse (Lund University) |
| Testing Properties of Edge DistributionsYumou Fei (MIT) |
| The communication complexity of distributed estimationParikshit Gopalan (Apple); Raghu Meka (UCLA); Prasad Raghavendra, Mihir Singhal (UC Berkeley); Avi Wigderson (Institute for Advanced Study) |
| The Complexity of Computing a Unique Nash EquilibriumAbheek Ghosh (Technical University of Munich); Paul W. Goldberg, Alexandros Hollender (University of Oxford) |
| The edge of the asymptotic spectrum of tensorsJosh Alman, Baitian Li, Kevin Pratt (Columbia University) |
| The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time ColoringYuta Inoue (The University of Tokyo); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Atsuyuki Miyashita (The University of Tokyo); Bojan Mohar (Simon Fraser University, Burnaby, Canada); Carsten Thomassen (Technical University of Denmark); Mikkel Thorup (University of Copenhagen) |
| The Instability of all Backoff ProtocolsLeslie Ann Goldberg (University of Oxford); John Lapinskas (University of Bristol) |
| The Keyl--Werner algorithm is not optimal for spectrum estimationAngelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley) |
| The Lov\'asz conjecture holds for moderately dense Cayley graphsBenjamin Bedert (Univeversity of Cambridge); Nemanja Draganic, Alp Muyesser (University of Oxford); Matias Pavez-Signe (University of Chile) |
| The Mystery Deepens: On the Query Complexity of Tarski Fixed PointsXi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University) |
| The optimal information complexity of VC learningSteve Hanneke, Juexiao Wang (Purdue University) |
| The Power of Two-Choice Linear ProbingAmir Azarmehr (Northeastern University); Michael Bender (Stony Brook University); William Kuszmaul, Rose Silver (Carnegie Mellon University) |
| The Price of Anarchy for Selfish Load BalancingXihan Deng (Shanghai Jiao Tong University); Yaonan Jin (Hong Kong University of Science and Technology); Wenqian Wang, Yuhao Zhang (Shanghai Jiao Tong University) |
| The Proof Analysis Problem for Constant-Depth FregeNoel Arteche (Lund University & University of Copenhagen); Susanna de Rezende (Lund University); Erfan Khaniki (University of Oxford); Kilian Risse (Lund University) |
| The Richness of CSP Non-redundancyJoshua Brakensiek (University of California, Berkeley); Venkatesan Guruswami (UC Berkeley); Bart Jansen (TU Eindhoven, the Netherlands); Victor Lagerkvist (Linköpings universitet); Magnus Wahlstrom (Royal Holloway, University of London, UK) |
| The Sample Complexity of Membership Inference and Privacy AuditingMahdi Haghifam (TTIC); Adam Smith (Boston University); Jonathan Ullman (Northeastern University) |
| Tight Bounds for Learning Polyhedra with a MarginShyamal Patel (Columbia University); Santosh Vempala (Georgia Tech) |
| Tight Quantum Lower Bound for k-DistinctnessAleksandrs Belovs (University of Latvia) |
| Towards a Unified Algorithmic Framework for Shannon's TheoremSayan Bhattacharya (University of Warwick, UK); Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (Nanjing University) |
| Truthful-in-Expectation Mechanisms for MMS ApproximationMoshe Babaioff (The Hebrew University of Jerusalem); Uriel Feige (Weizmann Institute of Science); Noam Manaker Morag (The Hebrew University of Jerusalem) |
| Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length StreamsCheng Jiang (MIT); Yinchen Liu (Tsinghua University); Huacheng Yu (Princeton University) |
| Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key ExchangeVinod Vaikuntanathan (MIT CSAIL); Or Zamir (Tel Aviv University) |
| Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-ApproximateYaowei Long (University of Michigan) |
| Weighted Treewidth on Minor-Free Graphs: Combinatorics and ApproximationDániel Marx (CISPA Helmholtz Center for Information Security); Michał Pilipczuk (University of Warsaw, Poland); Karol Węgrzycki (Max Planck Institute for Informatics) |
| Worst-case depth hierarchy for shallow quantum circuitsMin-Hsiu Hsieh, Michael de Oliveira (Hon Hai (Foxconn) Quantum Computing Research Center); Sathyawageeswar Subramanian (University of Oxford); Xingjian Zhang (University of Technology Sydney) |
| Zero-error information equals amortized communication complexityDaiki Suruga (CFT PAN) |
